#include <iostream>
#include <string>
using namespace std;

struct Node{
	string data;
	Node* next;
};

//遍历链表
void traversalLinked(Node* node){

	cout << "traversalLinked" << endl;
	while(node!=NULL ){
		cout << node->data << endl;
		if(node->next!=NULL)
			node = node->next;
		else
			break;
	}
}
//正向创建链表
Node* initLinked(int n){
	Node *head = new Node();
	Node *tmp =  new Node();
	for(int i=0; i<n; ++i){
		Node *node = new Node();
		node->data = to_string(i);
		cout << node->data << endl;
		tmp->next=node;
		tmp = node;
		if(i==0)
			head = tmp;
		cout << tmp->data << endl;
	}
	tmp->next = NULL;
	return head;
}
//反向创建链表
Node* initLinked_Reverse(int n){

	Node *tmp = new Node();
	tmp->next = NULL;
	for(int i=0; i<n; ++i){
		tmp->data = to_string(i);
		Node *node = new Node();
		node->next=tmp;
		cout << tmp->data << endl;
		tmp = node;
	}
	tmp->data = "H";
	return tmp;
}
//链表反转
Node* initLinked_Reverse(Node* node){

	Node *tmp = new Node();
	tmp->next = NULL;
	while(true){
		node = node->next;
		tmp->data = node->data;
		if(node->next==NULL)
			break;
		Node *_node = new Node();
		_node->next=tmp;
		cout << tmp->data << endl;
		tmp = _node;
	}
	tmp->data = "H";
	return tmp;
}

//递归
Node* reverse(Node* node){

}


int main()
{
	Node *node = initLinked_Reverse(20);
	traversalLinked(node);
	Node *noder = initLinked_Reverse(node);
	traversalLinked(noder);
   return 0;
}